package  com.vinjune.algorithm.sort;


/**
*@author 作者：zhangwenjun
*@version 创建时间：2015年12月9日 下午5:11:01
*类说明
*
*堆排序
*/

public class Heapsort {
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] h = new int[] {49,38,65,97,76,13,27,49};  //下标从0开始
		
		heapSort(h);
		
		for(int i=0;i<h.length;i++)
			System.out.print(h[i] + " ");
	}

	/**
	 * 堆排序
	 * @param h
	 */
	public static void heapSort(int[] h) { //堆采用数组存储表示
		//对数组h进行堆排序
		for(int i=h.length/2-1;i>=0;i--) //把h[0..h.length-1]建成大根堆
			heapAdjust(h, i, h.length-1);
		for(int j=h.length-1;j>=0;j--) {
			int temp = 0;		//辅助空间
			temp = h[0];       
			h[0] = h[j];       // 将堆顶元素和当前未经排序子序列h[0..j]中的最后一个记录交换
			h[j] = temp;
			
			heapAdjust(h, 0, j-1);  //将h[0..j-1]调整为大根堆
		}
	}
	
	private static void heapAdjust(int[] h, int s, int m) { //h[s..m]为需要调整的元素范围
		//h[s-1..m]满足堆的定义，现在需要调整h[s]使h[s..m]成为一个大根堆
		int temp = 0;
		temp = h[s];  
		for(int i=2*s;i<=m;i*=2) {
			if(i<m && h[i]<h[i+1])    //i应该为值较大的记录的下标
				i++;
			if(temp>=h[i])  //temp应该插入在位置s上
				break;
			h[s] = h[i];
			s = i ;
		}
		h[s] = temp;         //插入在此位置
	}
	

}


